IOI 1996 (Veszprem, Ungaria)
	
	1. Reteaua de scoli

Un numar oarecare de scoli sunt conectate in retea, intre ele stabilindu-se
anumite intelegeri. Fiecare scoala poseda o lista de scoli carora le
distribuie software ("scoli receptoare"). Daca B apare in lista scolii A, nu
este obligatoriu ca si A sa apara in lista scolii B.
Scrieti un program care calculeaza numarul minim de scoli care trebuie sa
primeasca cate o copie a unui nou software, pentru ca acesta sa ajunga la
toate scolile din retea, folosind intelegerile (subproblema A). Pentru
obiectivul urmator, trebuie sa ne asiguram ca trimitand copia unui nou
software catre o scoala aleasa arbitrar, acest software va ajunge la toate
scolile din retea. Pentru a realiza aceasta putem extinde listele
"scolilor receptoare" cu noi membri. Calculati numarul minim de extensii
care trebuiesc realizate astfel incat oricare ar fi scoala catre care
trimitem noul software, acesta va ajunge la toate celelalte scoli
(subproblema B). O extensie inseamna introducerea unui nou membru in lista
receptorilor unei scoli.

Intrare

 Prima linie a fisierului INPUT.TXT contine un intreg N: numarul scolilor
 din retea (2=F3N=F3100). Scolile sunt identificate de primele N numere int=
regi
 pozitive. Fiecare din urmatoarele N linii contine o lista de "scoli
 receptoare". Linia i+1 contine identificatorii "scolilor receptoare"
 corespunzatoare scolii i. Fiecare lista se termina cu un 0. O lista vida
 contine numai un 0 pe linie.

Iesire

 Programul va scrie doua linii in fisierul OUTPUT.TXT. Prima linie va
 contine solutia subproblemei A (un numar intreg pozitiv). A doua linie
 contine solutia subproblemei B.

Exemplu

Pentru fisierul INPUT.TXT:
5
2 4 3 0
4 5 0
0
0
1 0

fisierul OUTPUT.TXT va fi:
1
2
=====================================

Solutie (Mihai Stroe)

    Rezolvarea mea incearca sa reduca dimensiunile problemei, obtinind un nou
  graf, in care nodurile sunt componentele tare conexe ale grafului initial,
  iar arcele corespund existentei arcelor intre noduri din componente conexe
  diferite; evident, graful este aciclic, deoarece un ciclu ar induce o noua
  componenta.
    Primul punct se rezolva numarand componentele tare conexe in care nu intra
  arce; este evident ca un nod dintr-o astfel de componenta va avea drum catre
  oricare nod din componenta, iar componentele in care intra arce vor primi
  informatia de la celelalte.
    Am rezolvat punctul b) in modul urmator:
    - numar componentele in care nu intra arce (x);
    - numar componentele din care nu ies arce (y);
    - numarul de muchii cerut este maximul dintre cele doua numere obtinute.

    Fie n1 numarul componentelor din care ies, dar nu intra arce, (multimea
    m1), n2 numarul componentelor in care intra, dar nu ies arce, (multimea
    m2), n3 numarul componentelor in care nu intra si din care nu ies arce
    (multimea m3) si n4 numarul componentelor in care intra si din care ies
    arce (multimea m4). Componentele din m4 nu ne intereseaza, fiind legate
    de cel putin un element din m1 sau m2 (sau de alte componente din m4).
    Avem: x=n1+n3;
          y=n2+n3.
      Notam z=max(x,y).
      Legam fiecare varf din m2 de un varf din m3; astfel se elimina un nod
    din m2 si intra un altul, care se elimina din m3,n3 scazind cu o unitate;
    pasul se repeta pana cand n3=0.
      S-a ajuns la situatia in care avem n1 noduri in m1 si n2 noduri in m2.
      Se uneste fiecare nod din m2 cu un nod din m1, astfel incat sa nu existe
    inaintea unirii un drum intre nodul din m1 si cel din m2. La fiecare unire
    n1 si n2 scad cu o unitate. In final se unesc restul nodurilor ramase,
    doua cate doua, pana cand n1=0 sau n2=0; restul nodurilor se unesc cu
    oricare alt nod. In final toate nodurile se vor afla in m4 si in aceeasi
    componenta tare conexa.

      Metoda da valori mai mici decat cele asteptate la punctul b), la testele
    input-9.txt si input-a.txt. Am incercat sa verific cele doua teste prin
    introducerea muchiilor, conform algoritmului meu, si verificarea
    tare conexitatii; rezultatele obtinute de mine mi s-au parut corecte.
}

var a,b,floyd,ad:array[1..100,1..100]of byte;
    fdi,fde,di,de:array[1..100]of byte;
    i,x,y,nr,min,nrcomp,nrext,j,k,l,m,n,nrctc:longint;
    fi,fo:text;
    luate:set of byte;
    bb:boolean;
    ctc:array[1..100]of set of byte;
    ss:string;

procedure dofloyd;
var i,j,k:byte;
begin
  for k:=1 to n do
      for i:=1 to n do
          for j:=1 to n do
              if floyd[i,k]+floyd[k,j]=2 then floyd[i,j]:=1;
  for i:=1 to n do
      for j:=1 to n do
          if a[i,j]=1 then
             begin
               inc(fdi[j]);
               inc(fde[i]);
             end;
end;

procedure calcctc;
begin
  b:=a;
  floyd:=a;
  dofloyd;
  a:=floyd;
  for i:=1 to n do
      for j:=1 to n do
          if a[i,j]+a[j,i]=1 then
             begin
               a[i,j]:=0;
               a[j,i]:=0;
             end;
  nrctc:=0;
  luate:=[];
  for i:=1 to n do
      if not(i in luate) then
      begin
        inc(nrctc);
        ctc[nrctc]:=[i];
        for j:=1 to n do
            if a[i,j]=1 then
               ctc[nrctc]:=ctc[nrctc]+[j];
        luate:=luate+ctc[nrctc];
      end;
  a:=b;
  for i:=1 to nrctc do
      for j:=1 to nrctc do
          if i<>j then
             for k:=1 to n do
                 if k in ctc[i] then
                    for l:=1 to n do
                        if l in ctc[j] then
                           if a[k,l]=1 then
                              ad[i,j]:=1;
end;

begin
  assign(fi,'input.txt');
  reset(fi);
  readln(fi,n);
  nrcomp:=0;
  for i:=1 to n do
      begin
        read(fi,j);
        while j<>0 do
          begin
            a[i,j]:=1;
            inc(de[i]);
            inc(di[j]);
            read(fi,j);
          end;
        readln(fi);
      end;
  close(fi);
  fillchar(ad,sizeof(ad),0);
  calcctc;
  for i:=1 to nrctc do
      begin
        di[i]:=0;de[i]:=0;
        for j:=1 to nrctc do
            if ad[i,j]=1 then inc(de[i]);
        for j:=1 to nrctc do
            if ad[j,i]=1 then inc(di[i]);
      end;
  k:=0;l:=0;
  for i:=1 to nrctc do
      if (di[i]=0)and(de[i]<>0)then inc(k);
  for i:=1 to nrctc do
      if (de[i]=0)and(di[i]<>0)then inc(l);
  for i:=1 to nrctc do
      if de[i]+di[i]=0 then begin inc(k);inc(l);end;
  m:=k;
  if l>k then k:=l;
  if nrctc=1 then
  k:=0;
  assign(fo,'output.txt');
  rewrite(fo);
  writeln(fo,m);
  writeln(fo,k);
  close(fo);
end.
-------------------------------
